// Package 03-复制带随机指针的链表 main
// @Title 03-复制带随机指针的链表
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-14 11:23
// @Create  2022-01-14 11:23
package main

import "fmt"

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func main() {
	root3 := Node{
		3, nil, nil,
	}
	root2 := Node{
		2, &root3, nil,
	}
	root1 := Node{
		1, &root2, &root3,
	}
	root2.Random = &root1
	display(&root1)
	res := copyRandomList(&root1)
	display(res)
	fmt.Println("-----------")
	fmt.Println("-----------")
	res2 := copyRandomListO1(&root1)
	display(res2)
}

func display(head *Node) {
	for head != nil {
		fmt.Printf("%d\t", head.Val)
		if head.Random != nil {
			fmt.Printf("%d\t\n", head.Random.Val)
		} else {
			fmt.Printf(" \t\n")
		}
		head = head.Next
	}
}

//
//  copyRandomList
//  @Description: (深拷贝)复制一个带有随机指针的链表 使用哈希表冗余的数据结构实现
//  @param head：链表的头结点
//  @return *Node：
//
func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	nodeMap := make(map[*Node]*Node)
	pCopy := head
	temp := head
	for head != nil {
		tpNode := Node{
			head.Val,
			nil,
			nil,
		}
		nodeMap[head] = &tpNode // 对每一个节点进行克隆
		head = head.Next
	}
	for pCopy != nil {
		if _, ok := nodeMap[pCopy]; ok {
			// 处理应有的关系
			nodeMap[pCopy].Next = nodeMap[pCopy.Next]
			// 处理随机值的关系
			nodeMap[pCopy].Random = nodeMap[pCopy.Random]
		}
		pCopy = pCopy.Next
	}
	return nodeMap[temp]
}

//
//  copyRandomListO1
//  @Description: 不使用哈希表的形式来解决问题
//  @param head：
//  @return *Node：
//
func copyRandomListO1(head *Node) *Node {
	if head == nil {
		return nil
	}
	record1 := head

	record3 := head
	record4 := head
	for head != nil {
		// 对每个节点进行克隆
		curNext := head.Next
		copyNode := &Node{
			Val:    head.Val,
			Next:   curNext,
			Random: nil,
		}
		head.Next = copyNode
		head = curNext
	}
	// 处理克隆节点的关系
	for record1 != nil {
		nextOne := record1.Next
		if record1.Random == nil {
			nextOne.Random = nil
		} else {
			nextOne.Random = record1.Random.Next
		}
		record1 = nextOne.Next
	}
	record2 := record4.Next
	// 最后复原关系
	for record3 != nil && record3.Next != nil {
		nextOne := record3.Next
		t := nextOne.Next
		record3.Next = t
		if record3.Next != nil {
			nextOne.Next = record3.Next
		} else {
			nextOne.Next = nil
		}
		record3 = t
	}
	return record2
}
